/**
* 输入两个字符串，比如abdbcc和abc，输出第二个字符串在第一个字符串中的连接次序
* 即输出：125，146，145，146
* 例子中搜索得到a,b,c在第一个字符串中出现位置次序{1},{2,4},{5,6}
     1
  2     4
5   6 5   6
组合成：125，126，145，146
**/
#include <stdio.h>
#include <string.h>

/**
* 本函数应用递归
* p: 父字符串
* s: 子字符串
* print_arr: 保存位置
* p_len: 父字符串长度
* s_len: 子字符串长度
* print_arr_num: 打印字符串位置,当等于s_len说明本次找完了
* p_start_num: 父字符串查找位置
* s_start_num: 子字符串查找位置
**/
void PrintfArray(char *p, char *s, int *print_arr, int p_len, int s_len, int print_arr_num,
                 int p_start_num,int s_start_num)
{
  /* 之所以要用下面变量保存传入值,是因为递归时这些局部变量都会入栈,回归时需要用 */
  int i,j, pStartNum = p_start_num, sStartNum = s_start_num, printNum  = print_arr_num;
  
  if (printNum == s_len) { /* 当打印位置为子字符串长度则说明找完了 */
    for (i = 0;i < s_len;i++) {
      printf("%d", *(print_arr+i));
    }
    printf(",");
    return;
  }
  
  for (i = pStartNum;i < p_len;i++) { /* 循环遍历父字符串 */
    for (j = sStartNum;j < s_len;j++) { /* 循环遍历子字符串 */
      if (*(p+i) == *(s+j)) {
        //printf("<%d,%d>\n", i,j);
        print_arr[printNum] = i+1;
        pStartNum=i;
        sStartNum=j;
        PrintfArray(p,s,print_arr,p_len,s_len,printNum+1,pStartNum+1,sStartNum+1);
      }
    }
  }
}

int main(int argc, char *argv[])
{
  char ParString[] = "abdbcca";
  char SonString[] = "abc";
  int  print_arr[16]; /* 保证能装下SonString位数就行 */
  
  if (NULL == ParString || NULL == SonString) {
    return -1; // 字符串传参错误
  }
  
  int p_len = strlen(ParString);
  int s_len = strlen(SonString);
  
  if (s_len <= 0 || p_len <= 0) {
    return -1; // 字符串为空
  }
  
  PrintfArray(ParString, SonString, print_arr, p_len, s_len,0,0,0);
  printf("\n");
  return 0;
}
